#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Solution {
public:
    int memo[101][101] = { 0 };
    int dfs(int i, int j)
    {
        if (memo[i][j] != -1) return memo[i][j];
        if (i == 0 || j == 0)
        {
            memo[i][j] = 0;
            return 0;
        }
        if (i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return memo[i][j];
        }

        memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
        return memo[i][j];
    }

    int uniquePaths(int m, int n) {
        memset(memo, -1, sizeof(memo));
        return dfs(m, n);
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (nums[j] > nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }

    int _memo[2501] = { 0 };
    int n;
    int _dfs(int pos, vector<int>& nums)
    {
        if (_memo[pos] != 0) return _memo[pos];
        int mx = 1;
        for (int i = pos + 1; i < n; ++i)
        {
            if (nums[i] > nums[pos])
                mx = max(mx, _dfs(i, nums) + 1);
        }
        _memo[pos] = mx;
        return _memo[pos];
    }

    int lengthOfLIS(vector<int>& nums) {
        n = nums.size();
        int ret = 1;
        for (int i = 0; i < n; ++i)
        {
            ret = max(ret, _dfs(i, nums));
        }
        return ret;
    }

    int memo[201][201] = { 0 };
    int n;
    int dfs(int left, int right)
    {
        if (left >= right) return 0;
        if (memo[left][right] != 0) return memo[left][right];
        int ret = INT_MAX;
        for (int i = left; i < right; ++i)
        {
            ret = min(ret, max(dfs(left, i - 1), dfs(i + 1, right)) + i);
        }
        memo[left][right] = ret;
        return ret;
    }

    int getMoneyAmount(int _n) {
        n = _n;
        return dfs(1, _n);
    }

    int memo[201][201] = { 0 };
    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j] != 0) return memo[i][j];
        int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        int ret = 1;
        for (auto dic : dics)
        {
            int x = i + dic[0], y = j + dic[1];
            if (x >= 0 && x < matrix.size() && y >= 0 && y<matrix[0].size() && matrix[x][y]>matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ret = 0;
        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                ret = max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    };

    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> Q;
        int level = 0;
        if (root)
        {
            Q.push(root);
            level = 1;
        }
        vector<int> ret;
        while (level)
        {
            int mx = INT_MIN;
            while (level--)
            {
                TreeNode* front = Q.front();
                Q.pop();
                mx = max(mx, front->val);
                if (front->left)
                    Q.push(front->left);
                if (front->right)
                    Q.push(front->right);
            }
            ret.push_back(mx);
            level = Q.size();
        }
        return ret;
    }
};